#include "DynamicArray.h"

#include <stdio.h>
#include <stdlib.h>
struct DynamicArray
{
    ElementType *a;  //数组指针
    int capacity;  //数组容量
    int size; //元素个数
};


DArray *InitDArray(int capacity)    //结构体在堆上
{

    DArray *array = (DArray*)malloc(sizeof(DArray));   
    if(array == NULL)
    {
        printf("InitDArray malloc 申请失败！\n");
        return NULL;
    }
    array->size = 0;
    array->capacity = capacity;
    array->a = (ElementType*)malloc(sizeof(ElementType) * capacity);
    if(array->a == NULL)
    {
        printf("InitDArray malloc array申请失败！\n");
        free(array);     //要先把之前要的堆上空间释放掉再返回空指针，不然会内存泄漏
        return NULL;
    }
    return array;
}

void InsertTail(DArray *array,ElementType element)
{
    if(array->size >= array->capacity)
    {
        array->capacity *=2;
        ElementType *newPtr = realloc(array->a, sizeof(ElementType) * array->capacity);
        if(newPtr == NULL)
        {
            printf("扩容数组失败！不能进行插入\n");
            array->capacity /= 2;
            return;
        }
        array->a = newPtr;
    }

    array->a[array->size++] = element;
}




void PrintArray(DArray *array,void(*print)(ElementType))
{
    printf("size : %d     capacity : %d\n",array->size,array->capacity);
    if(print)
    {
        for(int i = 0;i < array->size;i++)
        {
            print(array->a[i]);
        }
    }
    printf("\n");
}

ElementType *FindByElemrnt(DArray*array,ElementType element)
{
    for(int i = 0;i < array->size;i++)
    {
        if(array->a[i] == element)
            return &array->a[i];
    }
    return NULL;
}


void RemoveByIndex(DArray *array,int index)
{
    if(index < 0 || index >= array->size)
    {
        printf("插入位置错误！\n");
        return;
    }
    for(int i = index;i < array->size;i++)
    {
        array->a[i] = array->a[i+1];
    }
    array->size--;
}
void RemoveByElement(DArray *array,ElementType element)
{
    for(int i = 0;i<array->size;i++)
    {
        if(array->a[i] == element)
        {
            RemoveByIndex(array,i);
            i--;
        }
    }
}





// void FastSort(ElementType *a,int start,int end,bool(*Compare)(void*,void*))
// {
//     if(start >= end)  //终止条件
//         return;
//      int left = start;
//      int right = end;
//      ElementType temp = a[left]; //将最左边的值定为基准值
//      while(left < right)
//      {
//         //右边往左动，找比基准值小的数
//         while (Compare(a[right],temp) && left < right) 
//             right--;
//         if(left < right)
//             a[left++] = a[right]; //把右边比基准值小的数扔到左边
//         //左边往有动，找比基准值大的数
//         while (Compare(temp,a[left]) && left < right) 
//             left++;
//         if(left < right)
//             a[right--] = a[left]; //把右边比基准值大的数扔到右边
//      }
//      a[left] = temp;
//      FastSort(a,start,left-1,Compare);
//      FastSort(a,right+1,end,Compare);
// }





// void Sort(DArray*a,bool(*Compare)(void*,void*))
// {
//     FastSort(a->a,0,a->size-1,Compare);
// }




void FreeDArray(DArray *array,void(*Free)(ElementType))
{
    if(Free)
    {
        for(int i=0;i<array->size;i++)
        {
            Free(array->a[i]);
        }
    }
    free(array->a);
    free(array);
}